import java.util.ArrayList;
import java.util.List;

//N 皇后
//测试链接：https://leetcode.cn/problems/n-queens/
public class SolveNQueens {
    List<List<String>> ans;
    boolean[] col, dig1, dig2; //分别判断列，主对角线和此对角线存不存在皇后
    char[][] path;
    int n;

    public List<List<String>> solveNQueens(int _n) {
        ans = new ArrayList<>();
        n = _n;
        col = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];

        path = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <n; j++) {
                path[i][j] = '.';
            }
        }
        dfs(0); //从第0行开始
        return ans;
    }

    public void dfs(int row) {
        if(row == n) {
            List<String> temp = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                temp.add(new String(path[i]));
            }
            ans.add(new ArrayList<>(temp));
            return;
        }

        //依次遍历每一列
        for(int i = 0; i < n; i++) {
            //检查当前位置[row][i]所对应的列，和两条对角线都不存在皇后
            if(col[i] == false && dig1[i-row+n] == false && dig2[i+row] == false) {
                path[row][i] = 'Q';
                col[i] = true;
                dig1[i-row+n] = true;
                dig2[i+row] = true;
                dfs(row+1);

                //恢复现场
                path[row][i] = '.';
                col[i] = false;
                dig1[i-row+n] = false;
                dig2[i+row] = false;
            }
        }
    }
}
